package com.huang.leetcode.stack;

import java.util.Stack;

/**
 * @Author：CreateSequence
 * @Date：2020-08-01 13:25
 * @Description：接雨水 题解：https://leetcode-cn.com/problems/trapping-rain-water/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-8/
 */
public class PB42 {

    public int trap(int[] height) {

        /**
         * 1.创建一个栈，用于保存柱子高度
         * 2.遍历柱子，如果栈空，就跳过判断直接入栈，并查找下一个，如果栈不空，就判断当前柱子高度与栈顶柱子高度大小：
         * 3.1 如果当前高度小于栈顶，就将当前柱子入栈，然后判断下一个
         * 3.2 如果当前高度大于栈顶，说明形成了一个水洼，将栈顶元素出栈，并且计算新栈顶（也就是原栈顶元素的下一个元素）与当前柱子间的水
         *
         * 举例：
         * 假设当前墙为a,上一堵（即原栈顶元素）墙为b，上上堵（即新栈顶元素）墙为c，
         * 则积水为：sum = d(a-c-1) * { min(a,c) - b }
         *        ____
         * ____   |  |
         * |  |___|  |
         * | c|  b| a|
         * -------------
         */

        int sum = 0;
        Stack<Integer> stack = new Stack<>();
        //指针指向当前遍历到的墙
        int cur = 0;

        while (cur < height.length) {

            //如果栈不为空，并且当前指向的墙高度大于栈顶高度
            while (!stack.isEmpty() && height[cur] > height[stack.peek()]) {
                int top = height[stack.pop()];
                //如果当前的墙之前只有一堵墙就直接让当前的墙入栈
                if (stack.isEmpty()) {
                    break;
                }
                //计算当前的墙和上上堵墙的距离
                int d = cur - stack.peek() - 1;
                //取最低的墙作为高
                int min = Math.min(height[stack.peek()], height[cur]);
                //计算高度：当前的墙和上上堵墙的距离 * （ 高 - 上堵墙的高 ）
                sum += d * (min - top);
            }

            //将当前墙的下标入栈
            stack.push(cur++);
        }

        return sum;
    }

}
